#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+10;
int n,m,num[MAXN<<1],h[MAXN<<1],tot,root[MAXN],cnt,L[30],R[30],cntl,cntr;
struct node
{
	int x,y,z;
	bool k;
}qu[MAXN];
struct point
{
	int lc,rc,val;
}a[2200010];
int lowbit(int x)
{
	return x&-x;
}
void update(int last,int l,int r,int &o,int v,int k)
{
	o=++cnt;
	a[o]=a[last];
	a[o].val+=k;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(v<=mid)update(a[last].lc,l,mid,a[o].lc,v,k);
	else update(a[last].rc,mid+1,r,a[o].rc,v,k);
	return;
}
int query(int l,int r,int k)
{
	if(l==r)return l;
	int suml=0,sumr=0,mid=(l+r)>>1;
	for(int i=1;i<=cntl;++i)suml+=a[a[L[i]].lc].val;
	for(int i=1;i<=cntr;++i)sumr+=a[a[R[i]].lc].val;
	if(sumr-suml>=k)
	{
		for(int i=1;i<=cntl;++i)L[i]=a[L[i]].lc;
		for(int i=1;i<=cntr;++i)R[i]=a[R[i]].lc;
		return query(l,mid,k);
	}
	else
	{
		for(int i=1;i<=cntl;++i)L[i]=a[L[i]].rc;
		for(int i=1;i<=cntr;++i)R[i]=a[R[i]].rc;
		return query(mid+1,r,k-sumr+suml);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&num[i]);
		h[i]=num[i];
	}
	tot=n;
	for(int i=1;i<=m;++i)
	{
		char temp[3];
		scanf("%s",temp);
		scanf("%d%d",&qu[i].x,&qu[i].y);
		if(temp[0]=='Q')
		{
			scanf("%d",&qu[i].z);
			qu[i].k=true;
		}
		else
			h[++tot]=qu[i].y;
	}
	sort(h+1,h+1+tot);
	tot=unique(h+1,h+1+tot)-h-1;
	for(int i=1;i<=n;++i)
	{
		int t=lower_bound(h+1,h+1+tot,num[i])-h;
		for(int j=i;j<=n;j+=lowbit(j))
			update(root[j],1,tot,root[j],t,1);
	}
	for(int i=1;i<=m;++i)
	{
		if(qu[i].k)
		{
			cntl=cntr=0;
			--qu[i].x;
			for(int j=qu[i].x;j;j-=lowbit(j))
				L[++cntl]=root[j];
			for(int j=qu[i].y;j;j-=lowbit(j))
				R[++cntr]=root[j];
			printf("%d\n",h[query(1,tot,qu[i].z)]);
		}
		else
		{
			int t=lower_bound(h+1,h+1+tot,num[qu[i].x])-h;
			for(int j=qu[i].x;j<=n;j+=lowbit(j))
				update(root[j],1,tot,root[j],t,-1);
			num[qu[i].x]=qu[i].y;
			t=lower_bound(h+1,h+1+tot,num[qu[i].x])-h;
			for(int j=qu[i].x;j<=n;j+=lowbit(j))
				update(root[j],1,tot,root[j],t,1);
		}
	}
	return 0;
}
